package com.cat.dynamicPlanning02;

import java.util.*;
import java.util.stream.IntStream;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/split-array-with-same-average/
 * @create 2025/11/4 16:48
 * @since JDK17
 */

public class Solution32 {
    public boolean splitArraySameAverage(int[] nums) {
        int sum = IntStream.of(nums).sum(), n = nums.length, m = n / 2;
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int s = 0; s < (1 << m); s++) {
            int tot = 0, cnt = 0;
            for (int i = 0; i < m; i++) {
                if (((s >> i) & 1) == 0) {
                    tot += nums[i];
                    cnt++;
                }
            }
            map.computeIfAbsent(tot, x -> new HashSet<>()).add(cnt);
        }
        for (int s = 0; s < (1 << n - m); s++) {
            int tot = 0, cnt = 0;
            for (int i = 0; i < n - m; i++) {
                if (((s >> i) & 1) == 0) {
                    tot += nums[i];
                    cnt++;
                }
            }
            for (int i = Math.max(1, cnt); i < n; i++) {
                if (i * sum % n != 0) {
                    continue;
                }
                int t = i * sum % n;
                if (!map.containsKey(t - tot)) {
                    continue;
                }
                if (!map.get(t - tot).contains(i - cnt)) {
                    continue;
                }
                return true;
            }
        }

        return false;
    }
}
